1. Field of the Invention
The present invention relates to data networking and specifically to scaling virtual local area networks (VLANs) in a data network.
2. Background Information
Many organizations, including businesses, governments and educational institutions, utilize data networks so that employees and others may share and exchange information and/or resources. A data network typically comprises a plurality of entities interconnected by means of one or more communications media. An entity may consist of any device, such as a computer, that “sources” (i.e., transmits) or “sinks” (i.e., receives) data frames over the communications media. A common type of data network is a local area network (“LAN”) which often refers to a privately owned network within a single building or campus. LANs typically employ a data communication protocol (LAN standard), such as Ethernet, FDDI or token ring, that defines the functions performed by layer-2 (L2) and layer-1 (L1) of a communications architecture (i.e., a protocol stack). As used herein, L2 and L1 correspond to the data-link layer and physical layer, respectively, of the Open Systems Interconnect—Reference Model (OSI-RM).
One or more intermediate network devices, such as bridges and switches, are often used to couple data networks (e.g., LANs) together and allow the corresponding entities in each data network to exchange information. For example, a network switch may be used to provide a “switching” function between two or more LANs. Here, the switch may contain a plurality of ports coupled to the LANs. The switching function may include receiving data from a sending entity at a source port from one LAN and transferring that data to at least one destination port for forwarding to one or more receiving entities in another LAN.
Ethernet
Ethernet is one of the most common LAN standards used today. The Institute of Electrical and Electronics Engineers (IEEE) has approved an Ethernet transmission standard (IEEE 802.3) for copper-based medium, often called 10Base-T, that is capable of transmitting data at 10 Megabits-per-second (Mbs). The IEEE has also approved a Fast Ethernet transmission standard (IEEE 802.3u), sometimes referred to as 100Base-T, which is capable of operating at 100 Mbs. Both 10Base-T and 100Base-T, however, are limited to cable lengths that are less than 100 meters.
In addition to the 10Base-T and 100Base-T standards, the IEEE has promulgated a Gigabit Ethernet standard (IEEE 802.3z/802.3ab) for transmitting data at 1000 Mbs. A fiber channel version of the Gigabit standard is often referred to as 1000Base-X and a long haul copper version is often called 1000Base-T. In addition to the substantially increased transmission rate, Gigabit Ethernet also supports cable lengths of up to 3000 meters. Gigabit Ethernet thus represents a potentially significant increase in the size or range of Ethernet LANs.
Spanning Tree Algorithm
Most data networks include redundant communications paths so that a failure of any given link does not isolate any portion of the network. Such networks are typically referred to as meshed or partially meshed networks. The existence of redundant links, however, may cause the formation of circuitous paths or “loops” within the network. Loops are highly undesirable because data frames may traverse the loops indefinitely.
Furthermore, some intermediate network devices, such as bridges or switches, replicate frames whose destination is not known, resulting in a proliferation of data frames along loops. The resulting traffic can overwhelm the network. Other intermediate network devices, such as routers, that operate at higher layers, such as layer-3 or the network layer of the OSI-RM, deliver data frames and learn the addresses of entities on the network differently than most bridges or switches. Thus, data traffic “switched” at high layers are generally not susceptible to sustained looping problems.
To avoid the formation of loops, most intermediate network devices, such as bridges or switches, execute a spanning tree protocol (STP) which allows them to calculate an active network topology that is loop-free (i.e., a tree) and yet connects every pair of LANs within the network (i.e., the tree is spanning). The STP is part of an earlier (legacy) version of the IEEE 802.1D standard and has been replaced by the Rapid Spanning Tree Protocol (RSTP) described below. In general, according to STP, intermediate network devices elect a single device within the network to be a “Root Bridge”. The STP takes advantage of the fact that each intermediate network device has a unique numerical identifier (bridge ID) by specifying that the Root Bridge is the intermediate network device with the lowest bridge ID. In addition, for each LAN coupled to any intermediate network device, exactly one port (a “Designated Port”) on one intermediate network device (a “Designated Bridge”) is elected. The Designated Bridge is typically the one closest to the Root Bridge. All ports on the Root Bridge are Designated Ports, and the Root Bridge is the Designated Bridge on all the LANs to which it has ports.
Each intermediate network device that is not a Root-Bridge also selects one port (a “Root Port”) from among its ports which gives the lowest cost path to the Root Bridge. The Root Ports and Designated Ports are selected for inclusion in the active topology and are placed in a “forwarding” state so that data frames may be forwarded to and from these ports and thus onto the LANs interconnecting the bridges and end stations of the network. Ports not included within the active topology are placed in a “blocking” state. When a port is in the blocking state, data frames will not be forwarded to or received from the port. A network administrator may also exclude a port from the spanning tree by placing it in a “disabled” state.
To obtain the information necessary to run the spanning tree protocol, intermediate network devices exchange special messages called bridge protocol data unit (BPDU) messages or simply BPDUs. BPDUs carry information, such as assumed root and lowest root path cost, used in computing the active topology. More specifically, upon start-up, each intermediate network device initially assumes itself to be the Root Bridge and transmits BPDUs accordingly. Upon receipt from a neighboring device, the BPDU's contents are examined and compared with similar information (e.g., assumed root and lowest root path cost) stored by the receiving bridge in memory. If the information from the received BPDU is “better” than the stored information, the intermediate network device adopts the better information and uses it in the BPDUs that it sends (adding the cost associated with the receiving port to the root path cost) from its ports, other than the port on which the better information was received. Although received BPDUs are not forwarded by intermediate network devices, the identifier of the Root Bridge is eventually propagated to and adopted by all intermediate network devices as described above, allowing them to select their Root Port and any Designated Port(s).
In order to adapt the active topology to changes and failures, the Root Bridge periodically (e.g., every “hello time”) generates and transmits BPDUs. In response to receiving BPDUs on their Root Ports, intermediate network devices generate and transmit their own BPDUs from their Designated Ports, if any. Thus, BPDUs are periodically propagated throughout the network, confirming the active topology. As BPDU information is updated and/or timed-out and the active topology is re-calculated, ports may transition from the blocking state to the forwarding state and vice-versa. That is, as a result of new BPDU information, a previously blocked port may learn that it should be in the forwarding state (e.g., it is now the Root Port or a Designated Port).
Rapid Spanning Tree Protocol
As noted above, the IEEE 802.1D has incorporated the RSTP to replace the legacy STP. Like STP, the RSTP selects one intermediate network device, such as a bridge, of a data network to be a Root Bridge and defines an active topology that provides complete connectivity among LANs while severing any loops. Each individual port of each intermediate network device is assigned a port role according to whether the port is to be part of the active topology. The port roles defined by RSTP include Root, Designated, Alternate and Backup. The port offering the best, e.g., lowest cost, path to the Root Port is assigned the Root Port Role. Each port offering an alternative, e.g., higher cost, path to the Root Bridge is assigned the Alternate Port Role. For each LAN, the one port providing the lowest cost path to the Root Bridge from that LAN is assigned the Designated Port Role, while all other ports coupled to the LAN are assigned the Root, Backup or, in some cases, the Alternate Port Roles. At the Root Bridge, all ports are assigned the Designated Port Role.
Those ports that have been assigned the Root Port and Designated Port Roles are placed in the forwarding state, while ports assigned the Alternate and Backup Roles are placed in a discarding state. A port assigned the Root Port Role can be rapidly transitioned to the forwarding state provided that ports assigned the Alternate Port Role are placed in the state. If a failure occurs on the port currently assigned the Root Port Role, a port assigned the Alternate Port Role can be reassigned to the Root Port Role and rapidly transitioned to the forwarding state, provided that the previous Root Port has been transitioned to the discarding state. A port assigned the Designated Port Role or a Backup Port that is to be reassigned to the Designated Port Role can be rapidly transitioned to the forwarding state, provided that the roles of the ports of the downstream intermediate network device are consistent with this port being assigned the Designated Port Role. The RSTP provides an explicit handshake to be used by neighboring intermediate network devices to confirm that a new Designated Port can rapidly transition to the forwarding state.
Like STP, intermediate network devices running RSTP also exchange BPDUs in order to determine which roles to assign to the intermediate network device's ports. The BPDUs are also utilized in the handshake employed to rapidly transition Designated Ports to the forwarding state.
Virtual Local Area Networks (VLANs)
A data network may also be segmented into a series of logical networks. For example, U.S. Pat. No. 5,394,402, issued Feb. 28, 1995 to Ross (the “'402 patent”), discloses an arrangement for associating any port of a switch with any particular network segment. Specifically, according to the '402 patent, any number of physical ports of a particular intermediate network device, such as a switch, may be associated with any number of groups within the device by using a virtual local area network (VLAN) arrangement that “virtually” associates the port with a particular VLAN designation. More specifically, the intermediate network device associates VLAN designations with its ports and further associates those VLAN designations with messages transmitted from any of the ports to which the VLAN designation has been assigned.
The VLAN designation for each port is stored in a memory portion of the intermediate network device such that every time a message is received on a given access port the VLAN designation for that port is associated with the message. Association is accomplished by a flow-processing element, which looks up the VLAN designation in the memory portion based on the particular access port at which the message was received. In many cases, it may be desirable to interconnect a plurality of these intermediate network devices in order to extend the VLAN associations of ports in the network. Those entities having the same VLAN designation function as if they are all part of the same LAN. VLAN-configured bridges are specifically configured to prevent message exchanges between parts of the network having different VLAN designations in order to preserve the boundaries of each VLAN. Nonetheless, intermediate network devices operating above L2 can relay messages between different VLAN segments.
In addition to the '402 patent, the IEEE promulgated a widely used standard titled “Virtual Bridged Local Area Networks” (IEEE 802.1Q) which is geared towards processing packets associated with VLANs. To preserve VLAN associations of messages transported across trunks or links in VLAN-aware networks, both Ross and the IEEE 802.1Q standard disclose appending a VLAN identifier (VID) field to the corresponding frames to associate a frame with a VLAN. The VID field defined by the IEEE 802.1Q standard supports up to 4096 VLANs.
Multiple Spanning Tree Protocol
The IEEE has incorporated a widely used Multiple Spanning Tree Protocol (MSTP) standard in the IEEE 802.1Q standard that may be used to provide STP features for networks that support VLANs. The MSTP organizes a network into Multiple Spanning Tree (MST) regions. Within each region, the MSTP establishes an Internal Spanning Tree (IST) which provides connectivity to all intermediate network devices, such as bridges, within the respective region and to the ISTs established within other regions. The IST established within each MST region also provides connectivity to the one Common Spanning Tree (CST) established outside of the MST regions by IEEE 802.1Q standard compatible intermediate network devices running STP or RSTP. The IST of a given MST region receives and sends BPDUs to the CST. Accordingly, all intermediate network devices of the network are connected by a single Common and Internal Spanning Tree (CIST). From the point of view of legacy or IEEE 802.1Q intermediate network devices, moreover, each MST region appears as a single “virtual bridge” on the CST.
Within each MST region, the MSTP compatible intermediate network devices establish a plurality of active topologies, each of which is called a Multiple Spanning Tree Instance (MSTI). The MSTP devices also assign or map each VLAN to one and only one of the MSTIs. Because VLANs may be assigned to different MSTIs, frames associated with different VLANs can take different paths through an MST region. The intermediate network devices may, but typically do not, compute a separate topology for every single VLAN, thereby conserving processor and memory resources. Each MSTI is basically a simple RSTP instance that exists only inside the respective Region, and the MSTIs do not interact outside of the Region.
MSTP, like the other spanning tree protocols, uses BPDUs to establish the ISTs and MSTIs as well as to define the boundaries of the different MST regions. The intermediate network devices do not send separate BPDUs for each MSTI. Instead, every MSTP BPDU carries the information needed to compute the active topology for all of the MSTIs defined with the respective Region. Each MSTI, moreover, has a corresponding identifier (ID) and the MSTI IDs are encoded into the intermediate network devices' bridge IDs. That is, each intermediate network device has a unique ID, as described above, and this ID is made up of a fixed portion and a settable portion. With MSTP, the settable portion of an intermediate network device's bridge ID is further organized to include a system ID extension. The system ID extension corresponds to the MSTI ID. The MSTP compatible intermediate network devices within a given Region will thus have a different bridge ID for each MSTI. For a given MSTI, the intermediate network device having the lowest bridge ID for that instance is elected the root. Thus, an MSTP compatible intermediate network device may be the root for one MSTI but not another within a given MST region.
Each intermediate network device running MSTP also has a single MST Configuration Identifier (ID) that consists of three attributes: an alphanumeric configuration name, a revision level and a VLAN mapping table that associates each of the potential 4096 VLANs to a corresponding MSTI. Each intermediate network device, moreover loads its MST Configuration ID into the BPDUs sourced by the bridge. Because intermediate network devices only need to know whether or not they are in the same MST region, they do not propagate the actual VLAN to MSTI tables in their BPDUs. Instead, the MST BPDUs carry only a digest of the VLAN to MSTI table or mappings. The digest is generated by applying the well-known MD-5 algorithm to the VLAN to MSTI table.
When an intermediate network device receives an MST BPDU, it extracts the MST Configuration ID contained therein, including the digest, and compares it with its own MST Configuration ID to determine whether it is in the same MST region as the intermediate network device that sent the MST BPDU. If the two MST Configuration IDs are the same, then the two intermediate network devices are in the same MST region. If, however, the two MST Configuration IDs have at least one non-matching attribute, i.e., either different configuration names, different revision levels and/or different computed digests, then the intermediate network device that received the BPDU concludes that it is in a different MST region than the intermediate network device that sourced the BPDU. A port of a MST compatible intermediate network device, moreover, is considered to be at the boundary of a MST region if the Designated Bridge is in a different MST region or if the port receives legacy BPDUs.
Service Provider/Core Networks
Service Providers (SPs) often provide various services to various customers in order to enable these customers to “link-up” remote portions of their data network via, e.g., Ethernet. In a typical arrangement, a SP provides one or more access networks that various remote points in the customer's network use to gain access to the SP's data network. A SP's access networks may be linked using a core network that may be part of the SP's network. Alternatively, the core network may be part of a carrier network provided by a separate carrier. The core network typically comprises one or more intermediate network devices, such as optical switches and/or routers, configured to implement a high-speed backbone data network.
A SP may provide VLAN services that enable a customer to define VLANs that span remote portions of the customer's network. Here, the SP may use a VID based on the IEEE 802.1Q standard to enable data associated with a customer's VLAN to be carried from a customer's local site to the customer's remote site via the access and core networks. Moreover, the MSTP may be used to manage spanning trees associated with the customer's VLANs.
One problem with using a VID based on the IEEE 802.1Q standard is that the total number of VLANs that may be carried is limited to 4096. Thus, the SP's network may be limited to supporting a total of 4096 VLANs for all of its customers. In today's high-speed-high-access networks, this poses a significant limitation for a SP.
Prior art techniques have addressed this limitation by expanding the size of the VID field to accommodate more than 4096 VLANs. However, expanding the VID field may make traffic carrying the expanded VID field incompatible with various standards used to process VLAN traffic and manage VLAN networks, such as the IEEE 802.1Q standard. Thus, these standards may not be available to networks that are configured to support an expanded VID field.
Since these standards may not be available, intermediate network devices may have to be reconfigured or replaced in order to process traffic using the expanding VID. Further, these reconfigured devices may not be interoperable with intermediate network devices that implement standards (e.g., IEEE 802.1Q) for processing VLAN traffic. Moreover, since the MSTP may not be available, a new protocol may have to be developed to manage the network's topology to ensure it is “loop free.” Developing and implementing a new protocol may be costly and once again affect the interoperability between intermediate network devices configured to manage spanning trees using the new protocol and other network devices that utilize standard protocols to manage spanning trees.